/*
 https://leetcode.cn/submissions/detail/373390812/
 03. 无重复字符的最长子串
 medium, 刘小康 2024.08.29
 滑动窗口
 */

class Solution
{
    // 查重
    vector<int> words;
public:
    Solution() :
        words(128, -1)
    {
        // 
    }
    int lengthOfLongestSubstring(string s)
    {
        if (s.size() == 0)
        {
            return 0;
        }
        if (s.size() == 1)
        {
            return 1;
        }
        int maxLength = 0, length = 1;
        words[s[0]] = 0;
        for (int i = 0, j = 1; j < s.size(); ++j)
        {
            // 重复了
            if (words[s[j]] != -1)
            {
                // 更新数据
                maxLength = maxLength > length ? maxLength : length;
                // 
                length -= words[s[j]] - i;
                for (int it = i; it < words[s[j]]; ++it)
                {
                    words[s[it]] = -1;
                }
                i = words[s[j]] + 1;
                words[s[j]] = j;
            }
            // 没重复
            else
            {
                words[s[j]] = j;
                ++length;
            }
        }
        return maxLength > length ? maxLength : length;
    }
};
